The present invention relates generally to digital computer systems, and more specifically to memory management of computer systems which utilize garbage collection.
Modern symbolic computing systems usually use a memory management technique called garbage collection. This technique involves allocating memory for objects from available free memory as they are requested, and returning memory to the pool of available memory when the objects can no longer be accessed.
The garbage collector is a process which runs independently of the applications which allocate memory and create garbage. A copying garbage collector is a process which, generally, scans through all of the currently accessible memory objects, and copies those which are accessible to a special location to be saved. Once this is done, all memory objects not so copied are garbage and can be reclaimed.
A copying garbage collector begins its collection operation by dividing the virtual memory space of the computer system into three logical spaces; oldspace, scavenge space, and newspace. Oldspace contains all of the objects which are to be collected. Scavenge space contains all of the pointers to oldspace objects, other than pointers within oldspace. Newspace contains objects which can be guaranteed not to point to objects in oldspace.
The garbage collector executes a processing sequence, often called a scavenger, which proceeds through scavenge space from one end to the other. When pointers to objects in oldspace are encountered, the objects pointed to are copied from oldspace to scavenge space, at a position ahead of the scavenger. When an object is copied from oldspace to scavenge space a forwarding pointer is stored in the vacated position in oldspace so that if another pointer to the same object is processed, the scavenger can simply change the other pointer to the new object location. When the scavenger reaches the end of scavenge space, all oldspace objects which are accessible have been copied out of oldspace. At this point, all of oldspace may be reclaimed.
The garbage collectors on many present computer systems are known as stop and collect garbage collectors. This type of process, as the name implies, causes normal operation of the system to cease while the garbage collection process is run. This greatly simplifies the collection process because objects are not being modified and created while the garbage collector is operating. However, such a system has the drawback that no useful processing can be done while the garbage collector is in operation. For large virtual address spaces, the time spent garbage collecting can be quite long. For example, systems having 10 to 60 megabytes can typically spend more than an hour for the garbage collection process.
Numerous incremental garbage collection systems have been implemented. These are primarily found on systems having hardware dedicated to symbolic processing. In general, the garbage collectors operate in a time-sharing arrangement with the normal system processes. This type of garbage collection is more difficult to implement, because care must be taken to insure that there is no unwanted interaction between the garbage collector and the normal system processes.
Since the length of time spent garbage collecting is proportional to the size of the address space being collected, some current garbage collection systems utilize the concept of generations of memory objects to collect less than the entire virtual memory space. This concept is based on the observation that a high proportion of newly created objects become garbage quickly, while old objects tend to stay. This can be envisioned simply by realizing that memory objects representing compiled system routines, such as compilers and window managers, rarely become garbage, while dynamic data structures of the currently operating program tend to become garbage relatively frequently. The idea behind generational garbage collection is to collect the young objects more frequently, thereby making more efficient use of the collector to make memory available.
A description of features desirable in a garbage collection system can be found in A Real-Time Garbage Collector Based on the Lifetimes of Objects, Lieberman and Hewitt, Communications of the ACM, volume 26, number 6, pp. 419-429, 1983. This paper describes one possible system using generations of objects to improve efficiency of garbage collection.
It is an object of the present invention to provide a garbage collection system which can simply and efficiently garbage collect a large virtual address space.
Therefore, according to the present invention, the virtual address space of a computer system is conceptually divided into a number of different generations. Most objects are classified by generations depending on their age within the system. Objects in older generations are not allowed to contain pointers directly to objects in younger generations. Instead, pointers are routed through indirection cells which are located in separate parts of the address space. Use of such indirection cells greatly simplifies the task of keeping track of pointers into oldspace and pointers between generations. When garbage collection is run on a given generation, all of the pointers into the space to be collected are contained in a relatively small number of indirection cells. It is necessary to scavenge only the spaces containing these indirection cells in order to accomplish the garbage collection process.
The novel features which characterize the present invention are defined by the appended claims. The foregoing and other objects and advantages of the present invention will hereafter appear, and for purposes of illustration, but not of limitation, a preferred embodiment is shown in the accompanying drawings.